\documentclass[E:/GsjzTle/main/main.tex]{subfiles}


\begin{document}

\begin{itemize}
\item
  一般的并查集，维护的是具有连通性、传递性的关系，例如\textbf{亲戚的亲戚是亲戚}。
\item
  但是，有时候，我们要维护另一种关系：\textbf{敌人的敌人是朋友}。种类并查集就是为了解决这个问题而诞生的。
\end{itemize}

\textbf{例题：}

动物界有 \(A\) , \(B\) , \(C\) 三种动物 , 其中 \(A\) 吃 \(B\) , \(B\) 吃
\(C\) , \(C\) 吃 \(A\)\\
现有 \(N\) 只动物，每只动物都只是 \(A\) , \(B\) , \(C\)
三种动物中的一种\\
还有 \(M\) 句话 , 每句话的形如 ： \(K\) , \(X\) , \(Y\)

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  如果 \(K = 1\) , 那么这句话的意思是编号为 \(X\) 和 编号为 \(Y\)
  的动物为同类
\item
  如果 \(K = 2\) , 那么这句话的意思是编号为 \(X\) 的动物吃编号为 \(Y\)
  的动物
\end{enumerate}

这 \(M\) 句话中有真有假 ,
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

\begin{itemize}
\item
  当前的话与前面的某些真的话冲突，就是假话
\item
  当前的话中 \(X\) 或 \(Y\) 比 \(N\) 大，就是假话
\item
  当前的话表示 \(X\) 吃 \(X\)，就是假话
\end{itemize}

问 \(M\) 句话中有多少句假话 ？ \\
\textbf{解：}

\begin{itemize}
\item
  定义 \(far[i]\) 表示编号为 \(i\) 的动物的种类(\(A、B\) \(or\) \(C\))
\item
  \(far[i + n]\) 表示 \(i\) 的捕食域(被 \(i\) 吃的动物的种类)
\item
  \(far[i + 2 × n]\) 表示 \(i\) 的天敌域(吃 \(i\) 的动物的种类)
\end{itemize}

这样就可以轻松维护 \textbf{亲戚的亲戚是亲戚} \textbf{敌人的敌人是朋友}
这种关系

\begin{lstlisting}
cin >> k >> x >> y;
if(x > n || y > n) res ++ ;	
else if(k == 1)
{
	// 如果 x 这类动物是 y 这类动物的食物  
	// 如果 x 这类动物是 y 这类动物的天敌 
	if(find(x) == find(y + n) || find(x) == find(y + 2 * n)) res ++ ;	
	else
	{
		// 它们是同类动物 , 那么它们的捕食域和天敌域就要合并 
		Union(x , y);
		Union(x + n , y + n);
		Union(x + 2 * n , y + 2 * n);
	}
}	
else 
{
	if(x == y || find(x) == find(y) || find(x) == find(y + n)) res ++ ;	
	else 
	{
		Union(x + n , y);		  // x 的捕食域加入 y
		Union(x , y + 2 * n); 	  // y 的天敌域加入 x
		Union(x + 2 * n , y + n); // x 的天敌域加入 y 的捕食域  
	}			
}
\end{verbatim}

\end{document}
